/**
 * @author: gao
 * @create-date: 2025/3/1 19:23
 */

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int postIndex = 0;

    public TreeNode buildTree(int[] inorder, int[] postorder){
        postIndex = postorder.length-1;
        return buildTreeChild(postorder,inorder,0, inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend){
        if(inbegin > inend){
            return null;
        }
        TreeNode root = new TreeNode(preorder[postIndex]);
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        return root;
    }
    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}